/**
 * Created with IntelliJ IDEA.
 * Description: 20250309：优选算法【位运算】
 * User: 姚东名
 * Date: 2025-03-09
 * Time: 7:31
 */
public class Demo2 {
    // 3.两个整数之和，使用位运算规则来算
    public int getSum(int a, int b) {
        // 进行循环
        while (b != 0) {
            // 保存进位
            // a & b 可以看作变成了 bit 位 变成了0，向左移动一位，模拟实现了 进位
            int carry = (a & b) << 1;

            // 无进位相加，异或运算
            a = a ^ b;

            b = carry;
        }
        return a;
    }
    // 2. 消失的数字
    public int missingNumber(int[] nums) {
        // 用位运算：异或运算规则做 -> 相同为 0 相异为 1
        int ret = 0;
        for (int x : nums) {
            // 将 数组 nums 中的 元素全都异或起来
            ret ^= x;
        }
        for (int i = 0; i <= nums.length; i++) { // n + 1 个元素
            // 将 0 ~ n 的元素都异或起来
            // 例如：9,6,4,2,3,5,7,0,1
            //      0 1 2 3 4 5 6 7 8 9
            //      相同的都直接消消乐了 所以 ret 最后肯定只剩下 那个在 nums 数组没有出现的元素
            ret ^= i;
        }
        return ret;
    }
    // 1. 判断字符是否唯一
    public boolean isUnique(String astr) {
        // 利用鸽巢原理 来做优化
        if (astr.length() > 26) {
            return false;
        }
        int bitMap = 0; // 位图原理：比特位 有 1 表示已经存在 0 表示还未存在
        for (int i = 0; i < astr.length(); i++) {
            // 判断 bit 位是否已经标志上 1 了
            int x = astr.charAt(i) - 'a'; // 算出应该放在哪个 bit 位上
            if (((bitMap >> x) & 1) == 1) {
                // 表示 bitMap >> x == 0 表示此时 该 bit 位 没有字符
                return false;
            }
            // 把当前字符加⼊到位图中
            bitMap |= (1 << x);
        }
        return true;
    }
    public static void main(String[] args) {

    }
}
